#include <iostream>
using namespace std;

struct Node {
    int val;
    Node *lch, *rch;
};


// 带有状态的递归, 实际上解决的是不断返回这个节点, 在递归中进行连接
Node* insert(Node* p, int x) {
    // 相当于在递归过程中重新连接一次
    if (p == NULL) {
        Node* n = new Node();
        n->lch = n->rch = NULL;
        n->val = x;
        return n;
    }
    if (x > p->val) return p->rch = insert(p->rch, x);
    return p->lch = insert(p->rch, x);
}

// 查找数值
Node *find(Node *p, int x) {
    if (p == NULL) return NULL;
    if (x > p->val) return find(p->rch, x);
    if (x < p->val) return find(p->lch, x);
    return p;
}

// 删除数值
Node *remove(Node *p, int x) {
    if (p == NULL) return NULL;
    if (x > p->val) return p->rch = remove(p->rch, x);
    if (x < p->val) return p->lch = remove(p->lch, x);
    else {
        if (p->lch == NULL) {
            // 提升右节点
            Node *q = p->rch;
            delete p;
            return q;
        }
        else if (p->lch->rch == NULL) {
            Node *q = p->lch;
            q->rch = p->rch;
            delete p;
            return q;
        }
        else {
            // 这个地方得考虑全面点
            
            Node *q;
            for (q = p->lch; q->rch->rch != NULL; q = q->rch);
            Node *r = q->rch;
            q->rch = r->lch;
            r->lch = p->lch;
            r->rch = p->rch;
            delete p;
            return r;
        }
        return p;
    }
}